#include <assert.h>
#include <iostream>
#include <stdlib.h>
using namespace std;
template <class T> T middle(T a, T b, T c);

template <class T> void quickSort(T* elts, int n);

template <class T>
void __quickSort(T* elts, int b, int e);

template <class T>
inline void __swap(T &a, T &b);

template <class T>
int __partition(T* elts, int b, int e);

template <class T>
inline void printArray(T* a, int n);

template <class T>
T middle(T a, T b, T c)
{
    if (a < b) {
        if (b < c) return b;
        else if (a < c) return c;
        else return a;
    } else {
        if (a < c) return a;
        else if (b < c) return c;
        else return b;
    }
}


template <class T>
void quickSort(T* elts, int n)
{
    if (elts == 0 || n == 0)
        return;
    __quickSort(elts, 0, n);

}
template <class T>
void __quickSort(T* elts, int b, int e)
{
    if ( b + 1 >= e)
        return;
    int mid = __partition(elts, b, e);
    __quickSort(elts, b, mid);
    __quickSort(elts, mid, e);
}
template <class T>
inline void __swap(T &a, T &b)
{
    T tmp = a;
    a = b;
    b = tmp;
}

template <class T>
int __partition(T* elts, int b, int e)
{
    int mid = b + (e - b) / 2;
    T midvalue = middle(elts[b], elts[mid], elts[e - 1]);
    int i = b, j = e - 1;
    while ( i <= j ){
        while (elts[i] < midvalue) i++;
        while ( midvalue < elts[j]) j--;
        if ( i <= j) {
            __swap(elts[i], elts[j]);
            i ++;
            j --;
        }
    }
    if ( i >= e) i = e - 1;
//    cout<<endl;
//    cout<<"mid:" << midvalue<<endl;
//    printArray(&elts[b], i - b);
//    cout<<endl;
//    printArray(&elts[i], e - i);
//    cout<<endl;
//    cout<<i << ":" << elts[i] << " ;" <<j << ":" <<  elts[j]<< endl;

    assert(b <= j);
    assert(i < e);
    assert(elts[j] <= midvalue);
    assert(elts[i] >= midvalue);

    return i;
}


void test_swap()
{
    int a = 1;
    int b = 2;
    __swap(a,b);
    assert(a == 2);
}

template <class T>
inline void printArray(T* a, int n)
{
    for(int i = 0; i < n; i ++)
        cout<<a[i]<<" ";
}
void test_partition()
{
    int a[] = {1,3,4,32,52,2,1,34,8,3,442};
    int mid = __partition(a, 0, sizeof(a)/sizeof(int));
    cout<<sizeof(a)/sizeof(int) << " " << mid<<":";
    printArray(a, sizeof(a)/sizeof(int));
    cout<<endl;
}
void test_sort()
{
    int a[] = {1,3,4,32,52,2,1,34,8,3,442};
    quickSort(a, sizeof(a)/sizeof(int));
    for (int i = 1; i < sizeof(a)/sizeof(int); i ++) {
        assert(a[i-1] <= a[i]);
    }
}


void test_middle()
{
    assert(1 == middle(1,1,1));

    assert(1 == middle(2,1,1));
    assert(1 == middle(1,2,1));
    assert(1 == middle(1,1,2));

    assert(1 == middle(0,1,1));
    assert(1 == middle(1,0,1));
    assert(1 == middle(1,1,0));

    assert(1 == middle(0,1,2));
    assert(1 == middle(1,0,2));
    assert(1 == middle(1,2,0));
}
